package me.huangxiang.data_structure_and_algorithm.tree;

public class BinSearchTree {
    private BinTreeNode root = null; // 用来存储当前这棵二叉搜索树的根节点
    private class BinTreeNode {
        public int data;
        public BinTreeNode lChild = null;
        public BinTreeNode rChild = null;

        public BinTreeNode(int data) {
            this.data = data;
        }
    }

    // 使用递归的方式实现二叉排序树的查找
    private boolean search(BinTreeNode node, int target){
        if (node == null){
            return false;
        }else if (node.data == target){
            return true;
        }else if (target < node.data){
            return search(node.lChild, target);
        }else {
            return search(node.rChild, target);
        }
    }

    public boolean search(int target){
        return search(root, target);
    }


    public boolean insert(int value){
        if (search(value)){
            return false; // 已经存在则返回保存不成功
        }else if (root == null){
            root = new BinTreeNode(value); // 单独处理根节点为空的情况
            return true;
        }else {
            BinTreeNode current = root;
            BinTreeNode parent = null;
            while (current != null){
                parent = current;
                if (value < current.data){
                    current = current.lChild;
                }else {
                    current = current.rChild;
                }
            }
            if (value < parent.data){
                parent.lChild = new BinTreeNode(value);
            }else {
                parent.rChild = new BinTreeNode(value);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] array = new int[]{5, 4, 7, 11, 13, 12};

        BinSearchTree binSearchTree = new BinSearchTree();
        for (int i = 0; i < array.length; i++){
            binSearchTree.insert(array[i]);
        }

        System.out.println("Is 7 contained in this array? " + binSearchTree.search(7));
        System.out.println("Is 34 contained in this array? " + binSearchTree.search(34));
    }
}
